package onlinebanking.math;

public class Polynomial {
	private class Term {
		Rational coefficent;
		int exponent;
		Term prev = null;
		Term next = null;

		Term(Rational coefficent, int exponent) {
			this.coefficent = coefficent;
			this.exponent = exponent;
		}

		public void connectMyPrev(Term t) {
			if (t != null) {
				this.prev = t;
				t.next = this;
			} else {
				System.out.println("No term to connect");
			}
		}

		public void connectMyNext(Term t) {
			if (t != null) {
				this.next = t;
				t.prev = this;
			} else {
				System.out.println("No term to connect");
			}
		}
	}

	/* Polynomial variables */
	private int degree;
	private Term head;
	private Term tail; // not a list as discussed in data structures :p
	
	public Polynomial(){
		this.degree = 0;
		this.head = null;
		this.tail = null;
	}
	
	public Polynomial(long coeff){
		this();
		long c[] = {coeff};
		this.constructPoly(c);
	}
	
	public Polynomial(long coeff[]){
		this();
		this.constructPoly(coeff);
	}
	
	public Polynomial(Rational coeff[]){
		this();
		this.constructPoly(coeff);
	}
	
	public void constructPoly(long coeff[]){
		Rational ratCoeff[] = new Rational[coeff.length];
		for(int i = 0; i<coeff.length ; i++){	//wrap integers into Rational objects
			ratCoeff[i] = new Rational(coeff[i]);
		}
		this.constructPoly(ratCoeff);
	}

	public void constructPoly(Rational coeff[]) {
		int degree = coeff.length - 1;
		this.setDegree(degree);
		
		int l = coeff.length;
		
		for (int i = degree; i >= 0; i--) {
			Term newterm = new Term(coeff[l - 1 - i], i);
			if (head == null) {
				head = newterm;
				tail = newterm;
			} else {
				tail.connectMyPrev(newterm);
				tail = newterm;
			}
		}
	}

	public long evaluatePoly(long x) {
		if (tail == null) {
			System.out.println("No terms to evaluate");
			return 0;
		}

		double y = 0.0;
		Term traverseptr = tail;
		long xpow = 1;
		while (traverseptr != head) {
			y += (traverseptr.coefficent.evaluate() * xpow);
			xpow *= x;
			traverseptr = traverseptr.next;
		}
		y += traverseptr.coefficent.evaluate() * xpow;

		//Remove cast to get an integer return type
		return (int)y;
	}

	public Rational[] getCoefficients() {
		Rational coeff[] = new Rational[this.degree + 1];

		Term traverseptr = head;
		for (int i = 0; traverseptr != null; i++) {
			coeff[i] = traverseptr.coefficent;
			traverseptr = traverseptr.prev;
		}
		return coeff;
	}

	public Polynomial add(Polynomial p) {
		Rational myCoeff[] = this.getCoefficients();
		Rational hisCoeff[] = p.getCoefficients();

		int sumlength = Math.max(myCoeff.length, hisCoeff.length);

		Rational sumCoeff[] = new Rational[sumlength];

		for (int i = 0; i < sumlength; i++) {
			Rational a = (i >= myCoeff.length) ? new Rational(0)
					: myCoeff[myCoeff.length - i - 1];
			Rational b = ((i >= hisCoeff.length) ? new Rational(0) : hisCoeff[hisCoeff.length - i
					- 1]);

			sumCoeff[sumCoeff.length - i - 1] = a.add(b);

		}

		Polynomial sum = new Polynomial();
		sum.constructPoly(sumCoeff);
		return sum;

	}

	public Polynomial multiply(Polynomial q){
		Polynomial p = this;
		Polynomial pq = new Polynomial();
		
		//check if multiplication by zero
		if(p.equals(0) || q.equals(0)){
			long coeff[] ={0};
			pq.constructPoly(coeff);
			return pq;
		}
		
		//determine degree of the resulting polynomial
		int newDegree = p.degree + q.degree;
		
		Rational pqcoeffs[] = new Rational[newDegree+1];
		Rational pcoeffs[] = p.getCoefficients();
		Rational qcoeffs[] = q.getCoefficients();
		
		//initialize product coefficients
		for(int i = 0; i<pqcoeffs.length;i++){
			pqcoeffs[i] = new Rational(0);
		}
		
		//multiply
		for(int i = pcoeffs.length -1  ; i >=0 ; i--){
			
			for(int j = qcoeffs.length -1; j >=0; j-- ){
				int termexponent = i+j;
				Rational product = pcoeffs[i].multiply(qcoeffs[j]);			
				pqcoeffs[termexponent] = pqcoeffs[termexponent].add(product);
			}
			
		}
		
		pq.constructPoly(pqcoeffs);
		return pq;
		
	}


	public void printPoly() {
		if (head == null)
			System.out.println("No terms in the polynomial");
		Term traverseptr = head;

		while (traverseptr != tail) {
			System.out.print(((traverseptr.coefficent.equals(1)) ? ""
					: traverseptr.coefficent + "")
					+ ((traverseptr.exponent == 1) ? "x + " : "x^"
							+ traverseptr.exponent + " + "));
			traverseptr = traverseptr.prev;
		}
		System.out.println(traverseptr.coefficent);
	}
	
	private void setDegree(int degree) {
		this.degree = degree;
	}

	public static void main(String[] args) {
		Polynomial f = new Polynomial();
		Polynomial f2 = new Polynomial();
		
		long sample[] = { 1, 2, 3, 0, -5 };
		long sample2[] = { 2,-5 };

		f.constructPoly(sample);
		f2.constructPoly(sample2);
		
		System.out.print("f(x) = ");
		f.printPoly();

		System.out.print("f2(x) = ");
		f2.printPoly();
		
		System.out.print("(f + f2)(x) = ");
		f.add(f2).printPoly();
		
		System.out.print("(f * f2)(x) = ");
		f.multiply(f2).printPoly();

		System.out.print("f(3) = ");
		long y = f.evaluatePoly(3);
		System.out.println(y);
		Rational c[] = f.getCoefficients();
		for (int i = 0; i < c.length; i++) {
			 System.out.println(c[i].evaluate());
		}
	}

}
